Early operating systems allowed users to run only one program at a time. Users ran a program, waited for it to finish, and then ran another one. Modem operating systems allow users to execute (run) more than one program at a time or even multiple copies of the same program at the same time. This change highlights a subtle distinction: the difference between a program and a process. A program is a static sequence of instructions whereas a process is the dynamic invocation of a program along with the system resources required for the program to run. Thus, a process, in the simplest terms, is an executing program.
Processes include one or more threads. A thread is the basic unit used by the operating system to allocate processor time. A thread can include any part of the process code, including parts currently being executed by another thread. A processor is capable of executing only one thread at a time. However, a multitasking operating system, i.e., an operating system that allows users to run multiple programs, appears to execute multiple programs at the same time. In reality, a multitasking operating system continually alternates among programs, executing a thread from one program, then a thread from another program, etc. As each thread finishes its subtask, the processor is given another thread to execute. The extraordinary speed of the processor provides the illusion that all of the threads execute at the same time. Multitasking increases the amount of work a system accomplishes because most programs do not require that threads continuously execute. For example, periodically, a thread stops executing and waits while a slow resource completes a data transfer or while another thread is using a resource it needs. When one thread must wait, multitasking allows another thread to execute, thus taking advantage of processor cycles that would otherwise be wasted. The use of spinlocks removes this advantage as discussed further hereinbelow.
Threads often require a way to communicate with one another to coordinate their activities. While there are many complex forms of communication among threads, the simplest form is a synchronization construct, which includes events, semaphores, timers, and mutexes. Synchronization refers to the ability of one thread to voluntarily stop executing and wait until another thread performs some operation. On a multiprocessor system, both threads can run simultaneously, each on its own processor. This situation may cause each thread to simultaneously compete for access to the same resource, thereby creating the possibility of a race condition. A race condition exists when a thread modifies a resource to an invalid state, and then another thread attempts to access that resource and use it in the invalid state. One way to coordinate these two threads is through a combination of synchronization constructs: a mutex and a condition variable. FIG. 1 illustrates this and other problems in greater detail.
A system 100 includes a customer 102, which is an individual communicating with a program 110 to purchase desired goods or services. The program 110 has one thread 104 of execution for creating sales orders based on the requests of the customer 102 and another thread 108 that takes sales orders to process them and ship goods to the customer 102. Access to a sales queue 106 is protected by a critical section to avoid the existence of a race condition. Race conditions can be prevented by identifying critical sections and enforcing mutual exclusion among threads. Critical sections are areas, such as the sales queue 106, where multiple threads 104, 108 can be executing simultaneously and these threads 104, 108 are making changes to shared data. Mutual exclusion is achieved when only one thread at a time is permitted to execute within the critical section.
Consider a situation where the thread 108 enters the critical section to take sales orders from the sales queue 106 and finds the sales queue 106 empty. There is nothing for the thread 108 to do until the thread 104 adds new sales orders to the sales queue 106. The thread 108 would preferably wait for the thread 104 to arrive with new sales orders. In order for the thread 104 to add new sales orders to the sales queue 106, the thread 104 must be able to enter the critical section presently occupied by the thread 108. Therefore, the thread 108 must unlock the mutex associated with the sales queue 106. To be apprised that the sales queue 106 is not empty, the thread 108 also must put itself on a waiting list and block itself from further execution. Both the unlocking of the mutex and the blocking of execution must occur atomically. If not, the thread 104 may enter the critical section (the sales queue 106) and leave without notifying the thread 108 that the sales queue 106 is non-empty.
The use of condition variables avoids such a problem. Waiting on a condition variable allows the acts of blocking the thread and unlocking the mutex to happen in one atomic operation. Conventional implementation of the waiting feature of a condition variable uses a spinlock to lock the condition variable before the acts of unlocking the mutex and blocking the thread can be executed. The main disadvantage of a spinlock is that the thread must loop continuously in the code until it can lock the condition variable. This is problematic for a multiprogramming system because a single microprocessor is shared among many processes and threads. The continuous loop of the spinlock robs precious microprocessor cycles that other processes and threads could otherwise use for completing their tasks.
When a system has only a few shared resources, the inefficiency caused by a few spinlocks may not be noticeable. But when a system requires numerous shared resources, the proliferation of spinlocks will detrimentally affect the performance of the system. Without a better synchronization construct to guard against race conditions while allowing better performance, users may no longer trust the system 100 to provide a desired computing environment. As a result, usage of the system 100 will diminish in the marketplace. Thus, there is a need for a system, method, and computer-readable medium for causing a thread to wait or for signaling a thread to execute while avoiding or reducing the foregoing and other problems associated with existing system.